package q673_findNumberOfLIS;

import java.util.Arrays;

public class Solution {
    /*
    此题的关键在于维护两个数组
    dp[i]：i之前（包括i）最长递增子序列的长度为dp[i]
    count[i]：以nums[i]为结尾的字符串，最长递增子序列的个数为count[i]

    如何更新count[i]呢？
    以nums[i]为结尾的字符串，最长递增子序列的个数为count[i]。
    那么在nums[i] > nums[j]前提下，如果在[0, i-1]的范围内，找到了j，使得dp[j] + 1 > dp[i]，说明找到了一个更长的递增子序列。
    此时count[i]相较于count[j]的关系就是count[i] = count[j]
    那么以j为结尾的子串的最长递增子序列的个数，就是最新的以i为结尾的子串的最长递增子序列的个数，即：count[i] = count[j]。
    例如 1 3 5 4当我们到达 4 时 在遍历 1 3 5时 发现有 4 > 3 那么此时4结尾的最长子序列个数应该是与3相同的 也就是1
    而如果遇到 1 3 2当我们到达2时 首先 有 3 > 1 此时以3结尾的最长序列数量是1
    而又发现2 > 1 那么此时如果仍然更新为1 显然不合理

    所以考虑新情况：
    在nums[i] > nums[j]前提下，如果在[0, i-1]的范围内，找到了j，使得dp[j] + 1 == dp[i]，说明找到了两个相同长度的递增子序列。
    要注意的是 dp代表的是以i结尾的最长子序列长度
    所以对于 1 3 2 到达2时候 首先遍历到1 发现2 > 1 此时dp[2] = 2 count = 1
    然后遍历3 此时不满足 2 > 3 不会进入判断
    那么以i为结尾的子串的最长递增子序列的个数 就应该加上以j为结尾的子串的最长递增子序列的个数，即：count[i] += count[j];

    此题的核心在于最后一次遍历 实际上是在找所有等于 maxCount长度的子串 他们的count[i]之和
     */
    public int findNumberOfLIS(int[] nums) {
        if (nums.length <= 1) return nums.length;
        int[] dp = new int[nums.length], count = new int[nums.length];
        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);

        int maxCount = 0;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j];
                    }
                }
                if (dp[i] > maxCount) maxCount = dp[i];
            }
        }

        int result = 0;
        for (int i = 0; i < nums.length; i++) {
            if (maxCount == dp[i]) result += count[i];
        }
        return result;
    }

    public static void main(String[] args) {
        Solution s= new Solution();
        s.findNumberOfLIS(new int[] {
            1,3,2
        });
    }

}
